package com.c2b.algorithm.leetcode.jzoffer.tree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/">II. 二叉树的最近公共祖先</a>
 * <p>
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 * </p>
 * <pre>
 *     例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]
 *                            3
 *                         /    \
 *                        5      1
 *                       / \    / \
 *                      6   2  0   8
 *                         /\
 *                        7  4
 * </pre>
 *
 * @author c2b
 * @since 2023/3/22 15:27
 */
public class JzOffer0068LowestCommonAncestor_II_S {


    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == root || q == root) {
            return root;
        }
        // 在左子树上查找最近公共祖先
        TreeNode l = lowestCommonAncestor2(root.left, p, q);
        // 在右子树上查找最近公共祖先
        TreeNode r = lowestCommonAncestor2(root.right, p, q);
        if (l == null) {
            // 说明公共祖先在右树上
            return r;
        } else {
            if (r == null) {
                return l;
            }
            return root;
        }
        //return l == null ? r : (r == null ? l : root);
    }

    /**
     * 存储父节点
     */
    public TreeNode lowestCommonAncestor(final TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        // 用map保存整棵树上节点的父节点
        Map<Integer, TreeNode> parentNodeMap = new HashMap<>();
        buildParentNodeMap(root, null, parentNodeMap);
        final List<Integer> pPath = new ArrayList<>();
        while (p != null) {
            pPath.add(p.val);
            p = parentNodeMap.get(p.val);
        }
        while (q != null) {
            if (pPath.contains(q.val)) {
                return q;
            }
            q = parentNodeMap.get(q.val);
        }
        return null;
    }

    /**
     * 构建key为当前节点，value为父节点的map
     *
     * @param currentNode 当前节点
     * @param parentNode  父节点
     * @param map         map
     * @author c2b
     * @since 2023/3/22 15:43
     */
    private void buildParentNodeMap(final TreeNode currentNode, final TreeNode parentNode, final Map<Integer, TreeNode> map) {
        if (currentNode != null) {
            map.put(currentNode.val, parentNode);
            buildParentNodeMap(currentNode.left, currentNode, map);
            buildParentNodeMap(currentNode.right, currentNode, map);
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);

        JzOffer0068LowestCommonAncestor_II_S jzOffer0068LowestCommonAncestor_ii_s = new JzOffer0068LowestCommonAncestor_II_S();
        System.out.println(jzOffer0068LowestCommonAncestor_ii_s.lowestCommonAncestor2(root, root.left.right, root.left.right).val);
    }
}
